In an increasing number of communication networks, a user's information is split into cells or packets independently of whether this information contains voice, video, or data signals, i.e., multimedia traffic. An already broadly standardized by CCITT and widely accepted example for cell based communication is the asynchronous transfer mode (ATM), which is able to support multimedia traffic with its different quality of service requirements. Two basic classes of service are being considered for ATM networks: reserved traffic with a guaranteed quality of service and best-effort traffic with no explicit guaranteed service. In the case of best-effort traffic class, sources or users are expected to specify only their peak rates at connection setup. The actual transmission is then adjusted according to the feedback provided by the network. The best-effort traffic is also called "available bit-rate" (ABR) traffic being allowed to use the bandwidth remaining after serving the guaranteed traffic.
The obvious advantages of cell based communication will lead to its introduction not only into wide area networking (WAN), but can be reasonably expected to be also the basis of future regional metropolitan area networks (MANs) and customer premises networks or local area networks (LANs). The LAN traffic is connectionless and delay insensitive. Data are transmitted without a prior connection establishment and the user traffic characteristics are not specified. The available bandwidth is shared among all the active users. This type of traffic falls therefore into the best-effort traffic category. Existing LANs can be interconnected by cell based networks, for example by ATM networks using a virtual channel (VC) or virtual path connection (VPC).
The main characteristic of best effort traffic is that it is bursty and it has an unpredictable behavior. In order to support an efficient statistical sharing of bandwidth among the competing users, a congestion control mechanism is required. Several congestion control mechanisms are known, such as the sliding window being used in the TCP INTERNET protocol. In a sliding window mechanism, a sender is allowed to transmit data in a window, the size of which is either fixed or adapted to the observed network or connection conditions. As the actual window size has to be transmitted from the receiver back to the sender, the sliding window scheme belongs in its most common variants to the so-called end-to-end flow control mechanisms. These types of flow control depend on the exchange of control signals or packets from the destination back to the source node. With signal delays and data transfer rates increasing due to the evolution of global networking, end-to-end schemes are expected to deteriorate in performance and to be replaced by hop-to-hop congestion controls.
As the name "hop-by-hop" suggests, in this approach control can be exercised at each node, link, switch, or gateway along the path of the traffic stream. The new flow control mechanism is of the hop-by-hop type. It belongs to a class of feedback control schemes which operate based on simple `stop` and `start` signals sent from the receiving node to the transmitting or upstream node. When the transmitting node receives a `stop` signal, it stops transmitting; it resumes transmission upon receipt of a `start` signal. Previously presented flow control schemes of this type are triggered by the status of the buffer(s) in which the incoming cells are temporarily stored for further transmission via an outgoing port of the node. Control signals are generated if the number of stored cells exceeds or falls below predetermined thresholds. Various applications of this mechanism are for example described in:
[1] Y. T. Wang and B. Sengupta, "Performance analysis of a feedback congestion control policy under non-negligible propagation delay," Proc. of ACM SIGCOMM '91, pp. 149-157, September 1991. PA0 [2] M. D. Schroeder, A. D. Birrell, M. Burrows, H. Murray, R. M. Needham, T. L. Rodeheffer, E. H. Satterthwaite, and C. P. Thacker, "Autonet: A high-speed, self-healing loacal area network using point-to-point links," IEEE J. Select. Areas Commun., vol. SAC-9, no. 8, pp. 1318-1335, October 1991. PA0 [3] J. Cherbonnier, D. Orsatti, and J. Calvignac, "Network backpressure flow control to support the best-effort service on ATM," Contribution to the ATM Forum, 93-1005, Stockholm, November 1993. PA0 [4] J. Calvignac, J. Cherbonnier, I. Iliadis, J.-Y. Le Boudec and D. Orsatti, "ATM best-effort service and its management in the LAN," Proc. EFOC&N '94, Heidelberg, Germany, June 1994.
According to these schemes and for a given connection, the receiving node sends a `stop` signal to the upstream node when the buffer content reaches a high-threshold H due to a cell arrival, and sends a `start` signal when the buffer content has subsequently dropped below a low-threshold L due to a cell departure. In order to avoid losses, the buffer should be able to accommodate all the in-transit cells which are sent before the `stop` signal arrives at the transmitting node. Therefore, these schemes require a buffer size B equal to H+r.multidot.D, where r denotes the peak transmission rate and D the round-trip propagation delay. In order to avoid starvation, i.e., a status in which the upstream node is still prevented from sending cells in the absence of any congestion, the low-threshold is selected such that the buffer can sustain a rate r for a round-trip period. Therefore, L is at least r.multidot.D. Both conditions together result in a minimum required buffer size for known flow control schemes of 2.multidot.r.multidot.D., to which further buffer space has to be added in order to increase the inertness of the control mechanism against small fluctuations of the level of the buffer occupation.
It is therefore an object of the invention to provide a hop-by-hop flow control mechanism, which has low buffer requirements and which further avoids a starvation situation in the upstream or sending nodes without adding an excessive amount of control signal (overhead) traffic to the network.